package Algorithm.dynamicProgramming.knapsackDp;

/**
 * 279. 完全平方数 https://leetcode.cn/problems/perfect-squares
 * 题目简述：只用完全平方数相加得到一个整数n，求所需的完全平方数的最小数量
 */
public class NumSquares {

    /**
     * 完全背包-装满最小价值问题。即从1至(int)Math.sqrt(n)的物品中取平方来装满背包n的最小数量
     * 1. 定义dp：dp[i][j]即为从前i个数中选装满背包j的最小数量
     * 2. 状态转移公式：分为以下两种情况，故dp[i][j] = min(dp[i-1][j], dp[i][j - i*i] + 1)，而物品最小重量为1，故无需考虑无法装满的情况
     *          （1）当不选第i个数时，dp[i][j] = dp[i-1][j]
     *          (2) 当选k个第i个数时，dp[i][j] = dp[i][j - i*i] + 1
     * 3. 初始化：dp[i][0] = 0;dp[0][j] = Integer.MAX_VALUE
     */
    public int numSquares(int n) {
        int m = (int) Math.sqrt(n);//m*m即能参与构成的最大完全平方数
        int[][] dp = new int[m+1][n+1];
        for (int j = 1;j <= n;j++)
            dp[0][j] = Integer.MAX_VALUE;
        for (int i = 1;i <= m;i++) {
            for (int j = 1;j <= n;j++) {
                if (j < i*i)//注意判断当前物品是否直接超过了背包负重
                    dp[i][j] = dp[i-1][j];
                else dp[i][j] = Math.min(dp[i-1][j], dp[i][j - i*i] + 1);
            }
        }
        return dp[m][n];
    }
}
